﻿//13.* Write a program that sorts an array of integers using the merge sort algorithm (find it in Wikipedia).


using System;
using System.Collections.Generic;

class MergeSort
{
    static void Main()
    {
        int numberN = int.Parse(Console.ReadLine());
        List<int> mergeList = new List<int>();
        for (int i = 0; i < numberN; i++)
        {
            mergeList.Add(int.Parse(Console.ReadLine()));
        }
        foreach (var item in MergeSplit(mergeList))
        {
            mergeList.Add(item);
            Console.WriteLine(item);
        }
    }

    static List<int> MergeSplit(List<int> mergeList)
    {
        List<int> left = new List<int>();
        List<int> right = new List<int>();
        int middle = mergeList.Count / 2;
        if (mergeList.Count <= 1)
        {
		        return mergeList;
        }
        else
        {
            for (int i = 0; i < middle; i++)
            {
                left.Add(mergeList[i]);
            }
            for (int i = middle; i < mergeList.Count; i++)
            {
                right.Add(mergeList[i]);
            }
        }
        left = MergeSplit(left);
        right = MergeSplit(right);
        return Merge(left, right);
    }

    static List<int> Merge(List<int> left, List<int> right)
    {
        List<int> result = new List<int>();
        while (left.Count > 0 || right.Count >0)
        {
            if (left.Count > 0 && right.Count >0)
            {
                if (left[0] <= right[0])
                {
                    result.Add(left[0]);
                    left.Remove(left[0]);
                }
                else
                {
                    result.Add(right[0]);
                    right.Remove(right[0]);
                }
            }
            else if (left.Count > 0)
            {
                result.Add(left[0]);
                left.Remove(left[0]);
            }
            else if (right.Count > 0)
            {
                result.Add(right[0]);
                right.Remove(right[0]);
            }
        }
        return result;
    }
}
